653E - Bear and Forgotten Tree 2 - CodeForces Solution

/*....
  sohith03
...*/  


#pragma GCC optimize ("O3,unroll-loops")
#pragma GCC target ("avx2")
#include <iostream>
#include<bits/stdc++.h>

using namespace std;

#define int long long
#define pb push_back
#define sz(x) (int)(x).size()
#define ln(x) (int)(x).length()
#define endl "\n"
//#define endl endl<<flush
#define ff first
#define ret return
#define ss second
#define lb lower_bound
#define ub upper_bound
#define yeno cout<<(ans?"YES":"NO")<<endl;
#define yess cout<<"YES"<<endl;
#define noo cout<<"NO"<<endl;
#define all(x) x.begin(),x.end()
#define ins insert
#define f(i,n) for(int i=0;i<n;i++)
#define f1(i,n) for(int i=1;i<=n;i++)
#define frev(i,n) for(int i=n-1;i>=0;i--)
#define frev1(i,n) for(int i=n;i>=1;i--)
#define out(x) cout<<x<<endl;
#define nl cout<<endl;
#define sout(x) cout<<x<<" ";
#define debug cout<<"hi"<<endl;


typedef pair<int,int> pr;
typedef vector<int> vint;

int in(){int n;cin>>n;return n;}
string sin(){string s;cin>>s;return s;}

const int M=1e6+7;
const int N=998244353;

void solve()
{
	int n,m,k;
	cin>>n>>m>>k;
	set<pr>fb;
	int deg=n-1;
	while(m--)
	{
		int x,y;
		cin>>x>>y;
		if(x==1||y==1)
		{
			deg--;
		}
		if(x>y)
		{
			swap(x,y);
		}
		fb.insert({x,y});
	}
	if(deg<k)
	{
		cout<<"impossible"<<endl;
		return;
	}
	set<int>s;
	for(int i=2;i<=n;i++)
	{
		s.ins(i);
	}
	function<bool(pr)>chk=[&](pr p)
	{
		return (fb.find(p)!=fb.end());
	};
	function<void(int)>dfs=[&](int r)
	{
		vector<int>rem;
		for(auto i:s)
		{
			if(!chk({min(i,r),max(i,r)}))
			{
				rem.pb(i);
			}
		}
		for(auto i:rem)
		{
			s.erase(i);
		}
		for(auto i:rem)
		{
			dfs(i);
		}
	};
	int comp=0;
	for(int i=2;i<=n;i++)
	{
		if((!chk({1,i}))&&(s.find(i)!=s.end()))
		{
			dfs(i);
			comp++;
		}
	}
	if(!s.empty())
	{
		cout<<"impossible"<<endl;
		return;
	}
	if(comp>k)
	{
		cout<<"impossible"<<endl;
		return;
	}
	
	cout<<"possible"<<endl;
}

int32_t  main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int t=1;
  //cin>>t;
  f(i,t)
  {
  	solve();
  }
return 0;
}